898F - Restoring the Expression - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef long double	ld;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl
#define set_dec(x)	    cout << fixed << setprecision(x);
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define int             long long

ll mod = 1000696969  ;

ll power(ll a, ll b)
{
    return (!b ? 1 : (b & 1 ? a * power(a * a % mod, b / 2) % mod : power(a * a % mod, b / 2) % mod));
}

const int N = 1e6+23;
ll hsh[N], pw[N];
ll base=10;
string s;
int n;


ll Hash(int l, int r){
    return ((hsh[r]-(hsh[l-1]*pw[r-l+1]%mod))%mod+mod)%mod;
}

bool zero(int l, int r){
    if(l==0){
        return 0;
    }
    if(r-l!=1  && s[l+1]=='0') return 0;

    if(r!=n-1 && s[r+1]=='0')return 0;



    return 1;


}

void solve(int a, int b){


    for (int i=1; i<=a; i++) cout<<s[i]; cout<<"+"; for (int i=a+1; i<=b; i++) cout<<s[i]; cout<<"="; for (int i=b+1; i<=n; i++) cout<<s[i]; cout<<endl;

    exit(0);
}

int32_t main()
{

    fast_io
    pw[0]=1;

    cin>>s;

    n=s.size();

    s="#"+s;


    for (int i=1; i<s.size(); i++){
        hsh[i]=(hsh[i-1]*base%mod+s[i]-'0')%mod;
        pw[i]=pw[i-1]*base%mod;
    }


    for (int i=2; i<=n-1; i++){

        int c=n-i;

        if(i<c)continue;


        ll sum=Hash(i+1, n);

        if((Hash(1,c)+Hash(c+1,i))%mod==sum && zero(c,i)) solve(c,i);
        //cout<<c<<" "<<i<<":"<<Hash(1,c)<<"+"<<Hash(c+1,i)<<"="<<sum<<endl;

		if((Hash(1,c-1)+Hash(c,i))%mod==sum && zero(c-1,i)) solve(c-1,i);

		if((Hash(1,i-c)+Hash(i-c+1,i))%mod==sum && zero(i-c,i)) solve(i-c,i);

		if((Hash(1,i-c+1)+Hash(i-c+2,i))%mod==sum && zero(i-c+1,i)) solve(i-c+1,i);




    }




}